package io.github.hadyang.leetcode.bytedance;

import java.util.Arrays;

/**
 * 数组中的第K个最大元素 在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
 *
 * <p>示例 1:
 *
 * <p>输入: [3,2,1,5,6,4] 和 k = 2 输出: 5 示例 2:
 *
 * <p>输入: [3,2,3,1,2,4,5,5,6] 和 k = 4 输出: 4 说明:
 *
 * <p>你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。
 *
 * @author haoyang.shi
 */
public class Array1018 {
  public static int findKthLargest(int[] nums, int k) {
    fastSort(nums, 0, nums.length - 1);
    return nums[nums.length - k];
  }

  public static void fastSort(int[] nums, int start, int end) {
    if (nums.length <= 1) {
      return;
    }

    if (start > end) {
      return;
    }

    if (end < 0 || start < 0 || end > nums.length - 1 || start > nums.length - 1) {
      return;
    }

    int left = start, right = end;
    int keyIndex = (left + right) / 2;

    while (left < right) {
      while (right > keyIndex && nums[right] > nums[keyIndex]) {
        right--;
      }

      if (right > keyIndex) {
        swap(nums, keyIndex, right);
        keyIndex = right;
      }

      while (left < keyIndex && nums[left] < nums[keyIndex]) {
        left++;
      }

      if (left < keyIndex) {
        swap(nums, left, keyIndex);
        keyIndex = left;
      }
      left++;
    }

    fastSort(nums, keyIndex + 1, end);
    fastSort(nums, start, keyIndex - 1);
  }

  private static void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
  }

  public static void main(String[] args) {
    int[] nums = {10, 293, 108, 161, 783, 376, 265, 330, 598, 646, 812};
    fastSort(nums, 0, nums.length - 1);

    System.out.println(Arrays.toString(nums));
  }
}
